SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Structured sparsity regularization</title>

</head>

Structured sparsity regularization

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">Structured sparsity regularization is a class of methods, and an area of research in <a href="Statistical_learning_theory" title="Statistical learning theory">statistical learning theory</a>, that extend and generalize sparsity regularization learning methods.<a href="#cite_note-rosPoggio-1">[1]</a> Both sparsity and structured sparsity regularization methods seek to exploit the assumption that the output variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> (i.e., response, or <a href="Dependent_and_independent_variables#Dependent_variable" title="Dependent and independent variables">dependent variable</a>) to be learned can be described by a reduced number of variables in the input space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> (i.e., the <a href="Domain_of_a_function" title="Domain of a function">domain</a>, space of <a href="Feature_(machine_learning)" title="Feature (machine learning)">features</a> or <a href="Dependent_and_independent_variables#Independent_variable" title="Dependent and independent variables">explanatory variables</a>). Sparsity regularization methods focus on selecting the input variables that best describe the output. Structured sparsity regularization methods generalize and extend sparsity regularization methods, by allowing for optimal selection over structures like groups or networks of input variables in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy">.<a href="#cite_note-groupLasso-2">[2]</a><a href="#cite_note-latentLasso-3">[3]</a>

Common motivation for the use of structured sparsity methods are model interpretability, <a href="Curse_of_dimensionality" title="Curse of dimensionality">high-dimensional learning</a> (where dimensionality of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"> may be higher than the number of observations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">), and reduction of <a href="Time_complexity" title="Time complexity">computational complexity</a>.<a href="#cite_note-LR18-4">[4]</a> Moreover, structured sparsity methods allow to incorporate prior assumptions on the structure of the input variables, such as overlapping groups,<a href="#cite_note-groupLasso-2">[2]</a> non-overlapping groups, and acyclic graphs.<a href="#cite_note-latentLasso-3">[3]</a> Examples of uses of structured sparsity methods include face recognition,<a href="#cite_note-face_recognition-5">[5]</a> <a href="Magnetic_resonance_imaging" title="Magnetic resonance imaging">magnetic resonance image (MRI)</a> processing,<a href="#cite_note-MRI-6">[6]</a> socio-linguistic analysis in natural language processing,<a href="#cite_note-sociolinguistic-7">[7]</a> and analysis of genetic expression in breast cancer.<a href="#cite_note-genetic-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Definition_and_related_concepts">Definition and related concepts</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Sparsity_regularization">Sparsity regularization</h3></div>

Consider the linear kernel <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularized</a> <a href="Empirical_risk_minimization" title="Empirical risk minimization">empirical risk minimization</a> problem with a loss function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(y_{i},f(x))}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(y_{i},f(x))}</annotation>

</semantics>

</math><img src="./83d7b03d4cfc2d42e0d09b00af44fda46a65495e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.987ex; height:2.843ex;" alt="{\displaystyle V(y_{i},f(x))}" loading="lazy"> and the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> "norm" as the regularization penalty:

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},\langle w,x_{i}\rangle )+\lambda \|w\|_{0},}</annotation>

</semantics>

</math><img src="./a9923b84d2050d19d9b4e81003056cc2b86aabb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:34.161ex; height:6.843ex;" alt="{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},\langle w,x_{i}\rangle )+\lambda \|w\|_{0},}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,w\in \mathbb {R^{d}} }">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,w\in \mathbb {R^{d}} }</annotation>

</semantics>

</math><img src="./7f0523dac6c9cc095c4bfdc00f1c56495f920342.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.693ex; height:3.009ex;" alt="{\displaystyle x,w\in \mathbb {R^{d}} }" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|w\|_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w\|_{0}}</annotation>

</semantics>

</math><img src="./8c88dffe8814e949d43dd9c949e26b1ebab06642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.043ex; height:2.843ex;" alt="{\displaystyle \|w\|_{0}}" loading="lazy"> denotes the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> "norm", defined as the number of nonzero entries of the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)=\langle w,x_{i}\rangle }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=\langle w,x_{i}\rangle }</annotation>

</semantics>

</math><img src="./11eb3a8a4c58a1372bcaf9aefa6747433a4c6369.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.153ex; height:2.843ex;" alt="{\displaystyle f(x)=\langle w,x_{i}\rangle }" loading="lazy"> is said to be sparse if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|w\|_{0}=s<d}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w\|_{0}=s<d}</annotation>

</semantics>

</math><img src="./6f98dfa823ca95766b61b584dbfafa118034788b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.547ex; height:2.843ex;" alt="{\displaystyle \|w\|_{0}=s<d}" loading="lazy">. Which means that the output <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"> can be described by a small subset of input variables.

More generally, assume a dictionary <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }</annotation>

</semantics>

</math><img src="./90269cd2db9aa54286e9e5a826f562fb7c4dc12d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.504ex; height:2.843ex;" alt="{\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=1,...,p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=1,...,p}</annotation>

</semantics>

</math><img src="./80fcb44828f4dfb719a067fd2ae1994d420e766f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:11.585ex; height:2.509ex;" alt="{\displaystyle j=1,...,p}" loading="lazy"> is given, such that the target function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation>

</semantics>

</math><img src="./202945cce41ecebb6f643f31d119c514bec7a074.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" loading="lazy"> of a learning problem can be written as:

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=\sum _{j=1}^{p}\phi _{j}(x)w_{j}}</annotation>

</semantics>

</math><img src="./252ae1db10e047c163e16d13dc51d0cf5edea9b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:19.266ex; height:7.343ex;" alt="{\displaystyle f(x)=\sum _{j=1}^{p}\phi _{j}(x)w_{j}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall x\in X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall x\in X}</annotation>

</semantics>

</math><img src="./84f06b5f8ad64618c77f852c72c9795c972fe86f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.443ex; height:2.176ex;" alt="{\displaystyle \forall x\in X}" loading="lazy"></dd></dl>

The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> norm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|f\|_{0}=\|w\|_{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|f\|_{0}=\|w\|_{0}}</annotation>

</semantics>

</math><img src="./07a00c99e8d33d9f9e5f516253f179c799cb181f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.799ex; height:2.843ex;" alt="{\displaystyle \|f\|_{0}=\|w\|_{0}}" loading="lazy"> as the number of non-zero components of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> is defined as

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w\|_{0}=|\{j|w_{j}\neq 0,j\in \{1,...,p\}\}|}</annotation>

</semantics>

</math><img src="./fdf6db15c8a071fffdc4026c3c00cf77241e9259.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:34.859ex; height:3.009ex;" alt="{\displaystyle \|w\|_{0}=|\{j|w_{j}\neq 0,j\in \{1,...,p\}\}|}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |A|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |A|}</annotation>

</semantics>

</math><img src="./648fce92f29d925f04d39244ccfe435320dfc6de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.037ex; height:2.843ex;" alt="{\displaystyle |A|}" loading="lazy"> is the cardinality of set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">.</dd></dl>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy"> is said to be sparse if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|f\|_{0}=\|w\|_{0}=s<d}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|f\|_{0}=\|w\|_{0}=s<d}</annotation>

</semantics>

</math><img src="./454018e201fa367de415692c25cab51cc2729384.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.303ex; height:2.843ex;" alt="{\displaystyle \|f\|_{0}=\|w\|_{0}=s<d}" loading="lazy">.

However, while using the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> norm for regularization favors sparser solutions, it is computationally difficult to use and additionally is not convex. A computationally more feasible norm that favors sparser solutions is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy"> norm; this has been shown to still favor sparser solutions and is additionally convex.<a href="#cite_note-LR18-4">[4]</a>

<div class="mw-heading mw-heading3"><h3 id="Structured_sparsity_regularization">Structured sparsity regularization</h3></div>

Structured sparsity regularization extends and generalizes the variable selection problem that characterizes sparsity regularization.<a href="#cite_note-groupLasso-2">[2]</a><a href="#cite_note-latentLasso-3">[3]</a> Consider the above <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularized</a> <a href="Empirical_risk_minimization" title="Empirical risk minimization">empirical risk minimization</a> problem with a general kernel and associated feature map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }</annotation>

</semantics>

</math><img src="./90269cd2db9aa54286e9e5a826f562fb7c4dc12d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.504ex; height:2.843ex;" alt="{\displaystyle \phi _{j}:X\rightarrow \mathbb {R} }" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=1,...,p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=1,...,p}</annotation>

</semantics>

</math><img src="./80fcb44828f4dfb719a067fd2ae1994d420e766f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:11.585ex; height:2.509ex;" alt="{\displaystyle j=1,...,p}" loading="lazy">.

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},\langle w,\Phi (x_{i})\rangle )+\lambda \|w\|_{0},}</annotation>

</semantics>

</math><img src="./3b2156dffe6001244351285ff786fab9ebae093c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:37.648ex; height:6.843ex;" alt="{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},\langle w,\Phi (x_{i})\rangle )+\lambda \|w\|_{0},}" loading="lazy"></dd></dl>

The regularization term <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lambda \|w\|_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda \|w\|_{0}}</annotation>

</semantics>

</math><img src="./fcb6cc6433aaf7761a80116458b304c3fbc9b71f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.399ex; height:2.843ex;" alt="{\displaystyle \lambda \|w\|_{0}}" loading="lazy"> penalizes each <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{j}}</annotation>

</semantics>

</math><img src="./326f4828cd2d8b281d5837f977d435d47450a191.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.574ex; height:2.343ex;" alt="{\displaystyle w_{j}}" loading="lazy"> component independently, which means that the algorithm will suppress input variables independently from each other.

In several situations we may want to impose more structure in the regularization process, so that, for example, input variables are suppressed according to predefined groups. Structured sparsity regularization methods allow to impose such structure by adding structure to the norms defining the regularization term.

<div class="mw-heading mw-heading2"><h2 id="Structures_and_norms">Structures and norms</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Non-overlapping_groups:_group_Lasso">Non-overlapping groups: group Lasso</h3></div>

The non-overlapping group case is the most basic instance of structured sparsity. In it, an a priori partition of the coefficient vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G}</annotation>

</semantics>

</math><img src="./f5f3c8921a3b352de45446a6789b104458c9f90b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.827ex; height:2.176ex;" alt="{\displaystyle G}" loading="lazy"> non-overlapping groups is assumed. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{g}}</annotation>

</semantics>

</math><img src="./3e28da8e516d060d7d6cef2ef308b1000a89c806.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.686ex; height:2.343ex;" alt="{\displaystyle w_{g}}" loading="lazy"> be the vector of coefficients in group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">, we can define a regularization term and its group norm as

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda R(w)=\lambda \sum _{g=1}^{G}\|w_{g}\|_{g}}</annotation>

</semantics>

</math><img src="./5d004aae2942ebb6c67c46ba2f26da18aae0449e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:21.207ex; height:7.676ex;" alt="{\displaystyle \lambda R(w)=\lambda \sum _{g=1}^{G}\|w_{g}\|_{g}}" loading="lazy">,</dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|w_{g}\|_{g}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w_{g}\|_{g}}</annotation>

</semantics>

</math><img src="./caa20035b148923253a6fa0cfeb159b93e135faf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.032ex; height:3.009ex;" alt="{\displaystyle \|w_{g}\|_{g}}" loading="lazy"> is the group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> norm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|w_{g}\|_{g}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msqrt>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w_{g}\|_{g}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}</annotation>

</semantics>

</math><img src="./ae0bf62a7cf3d2638ebf5f87f872eb4ba89a98cd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:20.488ex; height:8.676ex;" alt="{\displaystyle \|w_{g}\|_{g}={\sqrt {\sum _{j=1}^{|G_{g}|}(w_{g}^{j})^{2}}}}" loading="lazy"> , <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{g}}</annotation>

</semantics>

</math><img src="./39babf4e2b8ffd4e6de2ad6ed844325b35feea1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.848ex; height:2.843ex;" alt="{\displaystyle G_{g}}" loading="lazy"> is group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{g}^{j}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{g}^{j}}</annotation>

</semantics>

</math><img src="./11439526bf733f26294be9289ea9b68713b34712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.686ex; height:3.509ex;" alt="{\displaystyle w_{g}^{j}}" loading="lazy"> is the j-th component of group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{g}}</annotation>

</semantics>

</math><img src="./39babf4e2b8ffd4e6de2ad6ed844325b35feea1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.848ex; height:2.843ex;" alt="{\displaystyle G_{g}}" loading="lazy">.

The above norm is also referred to as group Lasso.<a href="#cite_note-groupLasso-2">[2]</a> This regularizer will force entire coefficient groups towards zero, rather than individual coefficients. As the groups are non-overlapping, the set of non-zero coefficients can be obtained as the union of the groups that were not set to zero, and conversely for the set of zero coefficients.

<div class="mw-heading mw-heading3"><h3 id="Overlapping_groups">Overlapping groups</h3></div>

Overlapping groups is the structure sparsity case where a variable can belong to more than one group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">. This case is often of interest as it can represent a more general class of relationships among variables than non-overlapping groups can, such as tree structures or other type of graphs.<a href="#cite_note-latentLasso-3">[3]</a><a href="#cite_note-genetic-8">[8]</a>

There are two types of overlapping group sparsity regularization approaches, which are used to model different types of input variable relationships:

<div class="mw-heading mw-heading4"><h4 id="Intersection_of_complements:_group_Lasso">Intersection of complements: group Lasso</h4></div>

The intersection of complements approach is used in cases when we want to select only those input variables that have positive coefficients in all groups they belong to. Consider again the group Lasso for a <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularized</a> <a href="Empirical_risk_minimization" title="Empirical risk minimization">empirical risk minimization</a> problem:

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lambda R(w)=\lambda \sum _{g=1}^{G}\|w_{g}\|_{g}}</annotation>

</semantics>

</math><img src="./5d004aae2942ebb6c67c46ba2f26da18aae0449e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:21.207ex; height:7.676ex;" alt="{\displaystyle \lambda R(w)=\lambda \sum _{g=1}^{G}\|w_{g}\|_{g}}" loading="lazy">,</dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|w_{g}\|_{g}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w_{g}\|_{g}}</annotation>

</semantics>

</math><img src="./caa20035b148923253a6fa0cfeb159b93e135faf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.032ex; height:3.009ex;" alt="{\displaystyle \|w_{g}\|_{g}}" loading="lazy"> is the group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> norm, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{g}}</annotation>

</semantics>

</math><img src="./39babf4e2b8ffd4e6de2ad6ed844325b35feea1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.848ex; height:2.843ex;" alt="{\displaystyle G_{g}}" loading="lazy"> is group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{g}^{j}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{g}^{j}}</annotation>

</semantics>

</math><img src="./11439526bf733f26294be9289ea9b68713b34712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.686ex; height:3.509ex;" alt="{\displaystyle w_{g}^{j}}" loading="lazy"> is the j-th component of group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{g}}</annotation>

</semantics>

</math><img src="./39babf4e2b8ffd4e6de2ad6ed844325b35feea1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.848ex; height:2.843ex;" alt="{\displaystyle G_{g}}" loading="lazy">.

As in the non-overlapping groups case, the group Lasso regularizer will potentially set entire groups of coefficients to zero. Selected variables are those with coefficients <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{j}>0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{j}>0}</annotation>

</semantics>

</math><img src="./46e186a52f4228f73fb876ca6a8b22a461c44be8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.835ex; height:2.843ex;" alt="{\displaystyle w_{j}>0}" loading="lazy">. However, as in this case groups may overlap, we take the intersection of the complements of those groups that are not set to zero.

This intersection of complements selection criteria implies the modeling choice that we allow some coefficients within a particular group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> to be set to zero, while others within the same group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> may remain positive. In other words, coefficients within a group may differ depending on the several group memberships that each variable within the group may have.

<div class="mw-heading mw-heading4"><h4 id="Union_of_groups:_latent_group_Lasso">Union of groups: latent group Lasso</h4></div>

A different approach is to consider union of groups for variable selection. This approach captures the modeling situation where variables can be selected as long as they belong at least to one group with positive coefficients. This modeling perspective implies that we want to preserve group structure.

The formulation of the union of groups approach is also referred to as latent group Lasso, and requires to modify the group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> norm considered above and introduce the following regularizer <a href="#cite_note-latentLasso-3">[3]</a>

<mrow>

<mrow>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(w)=inf\left\{\sum _{g}\|w_{g}\|_{g}:w=\sum _{g=1}^{G}{\bar {w}}_{g}\right\}}</annotation>

</semantics>

</math><img src="./594802d17bbe53d1bd38ef37143f4817236aad5a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:38.846ex; height:7.676ex;" alt="{\displaystyle R(w)=inf\left\{\sum _{g}\|w_{g}\|_{g}:w=\sum _{g=1}^{G}{\bar {w}}_{g}\right\}}" loading="lazy"></dd></dl>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in {\mathbb {R^{d}} }}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\in {\mathbb {R^{d}} }}</annotation>

</semantics>

</math><img src="./fdddb7b20a43c98dab3ba74169d3ced4317fa77d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.329ex; height:2.676ex;" alt="{\displaystyle w\in {\mathbb {R^{d}} }}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{g}\in G_{g}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{g}\in G_{g}}</annotation>

</semantics>

</math><img src="./a20f29e47020988d4403a46a69decc54d391f08d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.374ex; height:2.843ex;" alt="{\displaystyle w_{g}\in G_{g}}" loading="lazy"> is the vector of coefficients of group g, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {w}}_{g}\in {\mathbb {R^{d}} }}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {w}}_{g}\in {\mathbb {R^{d}} }}</annotation>

</semantics>

</math><img src="./175119495618e31c33f7aa25c065659e92cd5aad.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.35ex; height:3.343ex;" alt="{\displaystyle {\bar {w}}_{g}\in {\mathbb {R^{d}} }}" loading="lazy"> is a vector with coefficients <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{g}^{j}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{g}^{j}}</annotation>

</semantics>

</math><img src="./11439526bf733f26294be9289ea9b68713b34712.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.686ex; height:3.509ex;" alt="{\displaystyle w_{g}^{j}}" loading="lazy"> for all variables <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> in group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> , and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"> in all others, i.e., <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {w}}_{g}^{j}=w_{g}^{j}}">

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {w}}_{g}^{j}=w_{g}^{j}}</annotation>

</semantics>

</math><img src="./faa10b03ab12a6d93b4b561f0779c2f57cd493d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.47ex; height:3.509ex;" alt="{\displaystyle {\bar {w}}_{g}^{j}=w_{g}^{j}}" loading="lazy"> if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"> in group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g}</annotation>

</semantics>

</math><img src="./d3556280e66fe2c0d0140df20935a6f057381d77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.116ex; height:2.009ex;" alt="{\displaystyle g}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bar {w}}_{g}^{j}=0}">

<mover>

</mover>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\bar {w}}_{g}^{j}=0}</annotation>

</semantics>

</math><img src="./7e7eba048c728b35dc2b52312067cdd980b58347.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.946ex; height:3.509ex;" alt="{\displaystyle {\bar {w}}_{g}^{j}=0}" loading="lazy"> otherwise.

This regularizer can be interpreted as effectively replicating variables that belong to more than one group, therefore conserving group structure. As intended by the union of groups approach, requiring <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=\sum _{g=1}^{G}{\bar {w}}_{g}}">

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=\sum _{g=1}^{G}{\bar {w}}_{g}}</annotation>

</semantics>

</math><img src="./bb40a74b21a46ad5f54dc6af67d985d8822405b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:11.19ex; height:7.676ex;" alt="{\displaystyle w=\sum _{g=1}^{G}{\bar {w}}_{g}}" loading="lazy"> produces a vector of weights w that effectively sums up the weights of all variables across all groups they belong to.

<div class="mw-heading mw-heading3"><h3 id="Issues_with_Group_Lasso_regularization_and_alternative_approaches">Issues with Group Lasso regularization and alternative approaches</h3></div>

The objective function using group lasso consists of an error function, which is generally required to be convex but not necessarily strongly convex, and a group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy"> regularization term. An issue with this objective function is that it is convex but not necessarily strongly convex, and thus generally does not lead to unique solutions.<a href="#cite_note-:0-9">[9]</a>

An example of a way to fix this is to introduce the squared <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> norm of the weight vector as an additional regularization term while keeping the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy"> regularization term from the group lasso approach.<a href="#cite_note-:0-9">[9]</a> If the coefficient of the squared <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> norm term is greater than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy">, then because the squared <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> norm term is strongly convex, the resulting objective function will also be strongly convex.<a href="#cite_note-:0-9">[9]</a> Provided that the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> coefficient is suitably small but still positive, the weight vector minimizing the resulting objective function is generally very close to a weight vector that minimizes the objective function that would result from removing the group <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{2}}</annotation>

</semantics>

</math><img src="./85a4571ee9be10bd3c9df2480ab3d280f99e801a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{2}}" loading="lazy"> regularization term altogether from the original objective function; the latter scenario corresponds to the group Lasso approach.<a href="#cite_note-:0-9">[9]</a> Thus this approach allows for simpler optimization while maintaining sparsity.<a href="#cite_note-:0-9">[9]</a>

<div class="mw-heading mw-heading3"><h3 id="Norms_based_on_the_structure_over_Input_variables">Norms based on the structure over Input variables</h3></div>

See: <a href="Submodular_set_function" title="Submodular set function">Submodular set function</a>

Besides the norms discussed above, other norms used in structured sparsity methods include hierarchical norms and norms defined on grids. These norms arise from submodular functions and allow the incorporation of prior assumptions on the structure of the input variables. In the context of hierarchical norms, this structure can be represented as a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> over the variables while in the context of grid-based norms, the structure can be represented using a grid.<a href="#cite_note-:2-10">[10]</a><a href="#cite_note-:3-11">[11]</a><a href="#cite_note-:4-12">[12]</a><a href="#cite_note-:1-13">[13]</a><a href="#cite_note-:5-14">[14]</a><a href="#cite_note-:6-15">[15]</a>

<div class="mw-heading mw-heading4"><h4 id="Hierarchical_Norms">Hierarchical Norms</h4></div>

See: <a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a>

Unsupervised learning methods are often used to learn the parameters of <a href="Latent_variable_model" title="Latent variable model">latent variable models</a>. Latent variable models are statistical models where in addition to the observed variables, a set of latent variables also exists which is not observed. Often in such models, "hierarchies" are assumed between the variables of the system; this system of hierarchies can be represented using directed acyclic graphs.

Hierarchies of latent variables have emerged as a natural structure in several applications, notably to model text documents.<a href="#cite_note-:3-11">[11]</a> Hierarchical models using Bayesian non-parametric methods have been used to learn <a href="Topic_model" title="Topic model">topic models</a>,<a href="#cite_note-:2-10">[10]</a> which are statistical models for discovering the abstract "topics" that occur in a collection of documents. Hierarchies have also been considered in the context of kernel methods.<a href="#cite_note-:1-13">[13]</a> Hierarchical norms have been applied to bioinformatics,<a href="#cite_note-:4-12">[12]</a> computer vision and topic models.<a href="#cite_note-:5-14">[14]</a>

<div class="mw-heading mw-heading4"><h4 id="Norms_defined_on_grids">Norms defined on grids</h4></div>

If the structure assumed over variables is in the form of a 1D, 2D or 3D grid, then submodular functions based on overlapping groups can be considered as norms, leading to stable sets equal to rectangular or convex shapes.<a href="#cite_note-:1-13">[13]</a> Such methods have applications in computer vision<a href="#cite_note-:6-15">[15]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithms_for_computation">Algorithms for computation</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Best_subset_selection_problem">Best subset selection problem</h3></div>

The problem of choosing the best subset of input variables can be naturally formulated under a penalization framework as:<a href="#cite_note-LR18-4">[4]</a>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+\lambda \|w\|_{0},}</annotation>

</semantics>

</math><img src="./9258958672728f78955c9b994cabe3686a6e35b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:32.351ex; height:6.843ex;" alt="{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+\lambda \|w\|_{0},}" loading="lazy"></dd></dl>

Where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|w\|_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \|w\|_{0}}</annotation>

</semantics>

</math><img src="./8c88dffe8814e949d43dd9c949e26b1ebab06642.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.043ex; height:2.843ex;" alt="{\displaystyle \|w\|_{0}}" loading="lazy"> denotes the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> "norm", defined as the number of nonzero entries of the vector <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w}</annotation>

</semantics>

</math><img src="./88b1e0c8e1be5ebe69d18a8010676fa42d7961e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.664ex; height:1.676ex;" alt="{\displaystyle w}" loading="lazy">.

Although this formulation makes sense from a modeling perspective, it is computationally unfeasible, as it is equivalent to an exhaustive search evaluating all possible subsets of variables.<a href="#cite_note-LR18-4">[4]</a>

Two main approaches for solving the optimization problem are: 1) greedy methods, such as <a href="Stepwise_regression" title="Stepwise regression">step-wise regression</a> in statistics, or <a href="Matching_pursuit" title="Matching pursuit">matching pursuit</a> in <a href="Signal_processing" title="Signal processing">signal processing</a>; and 2) convex relaxation formulation approaches and <a href="Proximal_gradient_methods_for_learning" title="Proximal gradient methods for learning">proximal gradient</a> optimization methods.

<div class="mw-heading mw-heading3"><h3 id="Convex_relaxation">Convex relaxation</h3></div>

A natural approximation for the best subset selection problem is the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy"> norm regularization:<a href="#cite_note-LR18-4">[4]</a>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+\lambda \|w\|_{1}}</annotation>

</semantics>

</math><img src="./8b49d92a4ee89592c0af1dabc4948c850551cc45.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:31.705ex; height:6.843ex;" alt="{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+\lambda \|w\|_{1}}" loading="lazy"></dd></dl>

Such a scheme is called <a href="Basis_pursuit" title="Basis pursuit">basis pursuit</a> or the <a href="Lasso_(statistics)" title="Lasso (statistics)">Lasso</a>, which substitutes the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{0}}</annotation>

</semantics>

</math><img src="./d18f7cb79dd41b63d6aca9ec6b957c225a0aea81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{0}}" loading="lazy"> "norm" for the convex, non-differentiable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy"> norm.

<div class="mw-heading mw-heading3"><h3 id="Proximal_gradient_methods">Proximal gradient methods</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Proximal_gradient_methods_for_learning" title="Proximal gradient methods for learning">Proximal gradient methods</a></div>

<a href="Proximal_gradient_methods_for_learning" title="Proximal gradient methods for learning">Proximal gradient methods</a>, also called forward-backward splitting, are optimization methods useful for minimizing functions with a <a href="Convex_function" title="Convex function">convex</a> and <a href="Differentiable_function" title="Differentiable function">differentiable</a> component, and a convex potentially non-differentiable component.

As such, proximal gradient methods are useful for solving sparsity and structured sparsity regularization problems<a href="#cite_note-:0-9">[9]</a> of the following form:

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+R(w)}</annotation>

</semantics>

</math><img src="./5d5dbbdfd96662e946768a29d3f8a08f6f5976a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:30.544ex; height:6.843ex;" alt="{\displaystyle \min _{w\in \mathbb {R} ^{d}}{\frac {1}{n}}\sum _{i=1}^{n}V(y_{i},w,x_{i})+R(w)}" loading="lazy"></dd></dl>

Where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(y_{i},w,x_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(y_{i},w,x_{i})}</annotation>

</semantics>

</math><img src="./02df3b07a1890fe867213944db29ffd1c577a333.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.397ex; height:2.843ex;" alt="{\displaystyle V(y_{i},w,x_{i})}" loading="lazy"> is a convex and differentiable <a href="Loss_function" title="Loss function">loss function</a> like the <a href="Loss_function#Quadratic_loss_function" title="Loss function">quadratic loss</a>, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R(w)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R(w)}</annotation>

</semantics>

</math><img src="./e45c97c0143ecc12a2c8b8e87b5c6ffe1870b065.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.237ex; height:2.843ex;" alt="{\displaystyle R(w)}" loading="lazy"> is a convex potentially non-differentiable regularizer such as the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ell _{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ell _{1}}</annotation>

</semantics>

</math><img src="./361ddd720474aa41cb05453e03424fb7999d3b02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.024ex; height:2.509ex;" alt="{\displaystyle \ell _{1}}" loading="lazy"> norm.

<div class="mw-heading mw-heading2"><h2 id="Connections_to_Other_Areas_of_Machine_Learning">Connections to Other Areas of Machine Learning</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Connection_to_Multiple_Kernel_Learning">Connection to Multiple Kernel Learning</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Multiple_kernel_learning" title="Multiple kernel learning">Multiple kernel learning</a></div>

Structured Sparsity regularization can be applied in the context of <a href="Multiple_kernel_learning" title="Multiple kernel learning">multiple kernel learning</a>.<a href="#cite_note-:7-16">[16]</a> Multiple kernel learning refers to a set of machine learning methods that use a predefined set of kernels and learn an optimal linear or non-linear combination of kernels as part of the algorithm.

In the algorithms mentioned above, a whole space was taken into consideration at once and was partitioned into groups, i.e. subspaces. A complementary point of view is to consider the case in which distinct spaces are combined to obtain a new one. It is useful to discuss this idea considering finite dictionaries. Finite dictionaries with linearly independent elements - these elements are also known as atoms - refer to finite sets of linearly independent basis functions, the linear combinations of which define hypothesis spaces. Finite dictionaries can be used to define specific kernels, as will be shown.<a href="#cite_note-:7-16">[16]</a> Assume for this example that rather than only one dictionary, several finite dictionaries are considered.

For simplicity, the case in which there are only two dictionaries <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A=\{a_{j}:X\rightarrow \mathbb {R} ,j=1,...,p\}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A=\{a_{j}:X\rightarrow \mathbb {R} ,j=1,...,p\}}</annotation>

</semantics>

</math><img src="./6c15c4fea235adda95bc2b25abd283a62c59da9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:31.107ex; height:3.009ex;" alt="{\displaystyle A=\{a_{j}:X\rightarrow \mathbb {R} ,j=1,...,p\}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=\{b_{t}:X\rightarrow \mathbb {R} ,t=1,...,q\}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B=\{b_{t}:X\rightarrow \mathbb {R} ,t=1,...,q\}}</annotation>

</semantics>

</math><img src="./26a660a0ad829660f8fd4581da271b29c06a1fcf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.594ex; height:2.843ex;" alt="{\displaystyle B=\{b_{t}:X\rightarrow \mathbb {R} ,t=1,...,q\}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> are integers, will be considered. The atoms in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> as well as the atoms in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy"> are assumed to be linearly independent. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=\{d_{k}:X\rightarrow \mathbb {R} ,k=1,...,p+q\}=A\cup B}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D=\{d_{k}:X\rightarrow \mathbb {R} ,k=1,...,p+q\}=A\cup B}</annotation>

</semantics>

</math><img src="./df0ecd0277988447a792f7b4a77b3e27ea0a9f43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.798ex; height:2.843ex;" alt="{\displaystyle D=\{d_{k}:X\rightarrow \mathbb {R} ,k=1,...,p+q\}=A\cup B}" loading="lazy"> be the union of the two dictionaries. Consider the linear space of functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> given by linear combinations of the form

</mrow>

</mrow>

</munderover>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x)=\sum _{i=1}^{p+q}{w^{j}d_{j}(x)}=\sum _{j=1}^{p}{w_{A}^{j}a_{j}(x)}+\sum _{t=1}^{q}{w_{B}^{t}b_{t}(x)},x\in X}</annotation>

</semantics>

</math><img src="./b108cebd217f55fdaead027e2a2a649ca3974f34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:56.211ex; height:7.509ex;" alt="{\displaystyle f(x)=\sum _{i=1}^{p+q}{w^{j}d_{j}(x)}=\sum _{j=1}^{p}{w_{A}^{j}a_{j}(x)}+\sum _{t=1}^{q}{w_{B}^{t}b_{t}(x)},x\in X}" loading="lazy">

for some coefficient vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w_{A}\in \mathbb {R} ^{p},w_{B}\in \mathbb {R} ^{q}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{A}\in \mathbb {R} ^{p},w_{B}\in \mathbb {R} ^{q}}</annotation>

</semantics>

</math><img src="./dd1535b4c2ccd83a39640170391dc93ab46100a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.392ex; height:2.676ex;" alt="{\displaystyle w_{A}\in \mathbb {R} ^{p},w_{B}\in \mathbb {R} ^{q}}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=(w_{A},w_{B})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=(w_{A},w_{B})}</annotation>

</semantics>

</math><img src="./2ff3ede2b0efdb419c5995218cd050e265e8e761.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.879ex; height:2.843ex;" alt="{\displaystyle w=(w_{A},w_{B})}" loading="lazy">. Assume the atoms in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"> to still be linearly independent, or equivalently, that the map <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=(w_{A},w_{B})\mapsto f}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=(w_{A},w_{B})\mapsto f}</annotation>

</semantics>

</math><img src="./0a93caa839f0aeeb5764d6f67340351fec907a2d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.771ex; height:2.843ex;" alt="{\displaystyle w=(w_{A},w_{B})\mapsto f}" loading="lazy"> is one to one. The functions in the space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> can be seen as the sums of two components, one in the space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{A}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{A}}</annotation>

</semantics>

</math><img src="./b3f561a051435337d6fd20d1b3a2cb945fe97f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.396ex; height:2.509ex;" alt="{\displaystyle H_{A}}" loading="lazy">, the linear combinations of atoms in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> and one in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{B}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{B}}</annotation>

</semantics>

</math><img src="./824d31f712318ce157dfeb6dad19be3bfe66a59b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.411ex; height:2.509ex;" alt="{\displaystyle H_{B}}" loading="lazy">, the linear combinations of the atoms in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B}</annotation>

</semantics>

</math><img src="./47136aad860d145f75f3eed3022df827cee94d7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle B}" loading="lazy">.

One choice of norm on this space is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ||f||=||w_{A}||+||w_{B}||}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ||f||=||w_{A}||+||w_{B}||}</annotation>

</semantics>

</math><img src="./62b39af9f05446cf5b38ffe8f88a4838dcd5dc12.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.252ex; height:2.843ex;" alt="{\displaystyle ||f||=||w_{A}||+||w_{B}||}" loading="lazy">. Note that we can now view <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> as a function space in which <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{A}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{A}}</annotation>

</semantics>

</math><img src="./b3f561a051435337d6fd20d1b3a2cb945fe97f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.396ex; height:2.509ex;" alt="{\displaystyle H_{A}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{B}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{B}}</annotation>

</semantics>

</math><img src="./824d31f712318ce157dfeb6dad19be3bfe66a59b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.411ex; height:2.509ex;" alt="{\displaystyle H_{B}}" loading="lazy"> are subspaces. In view of the linear independence assumption, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> can be identified with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{p+q}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{p+q}}</annotation>

</semantics>

</math><img src="./cad5d193f0b4a5800ea21241a5b6b2a94b916cbb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.772ex; height:2.509ex;" alt="{\displaystyle \mathbb {R} ^{p+q}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{A},H_{B}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{A},H_{B}}</annotation>

</semantics>

</math><img src="./eaf75273e13e796d2d7ae0bcb76866835a7829ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.841ex; height:2.509ex;" alt="{\displaystyle H_{A},H_{B}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{p},\mathbb {R} ^{q}}">

<msup>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{p},\mathbb {R} ^{q}}</annotation>

</semantics>

</math><img src="./05dfa4fc1bd991fff66ab2b7c7f9f0e975cae84f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.438ex; height:2.676ex;" alt="{\displaystyle \mathbb {R} ^{p},\mathbb {R} ^{q}}" loading="lazy"> respectively. The norm mentioned above can be seen as the group norm in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy">associated to the subspaces <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{A}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{A}}</annotation>

</semantics>

</math><img src="./b3f561a051435337d6fd20d1b3a2cb945fe97f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.396ex; height:2.509ex;" alt="{\displaystyle H_{A}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{B}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{B}}</annotation>

</semantics>

</math><img src="./824d31f712318ce157dfeb6dad19be3bfe66a59b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.411ex; height:2.509ex;" alt="{\displaystyle H_{B}}" loading="lazy">, providing a connection to structured sparsity regularization.

Here, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{A}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{A}}</annotation>

</semantics>

</math><img src="./b3f561a051435337d6fd20d1b3a2cb945fe97f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.396ex; height:2.509ex;" alt="{\displaystyle H_{A}}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{B}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{B}}</annotation>

</semantics>

</math><img src="./824d31f712318ce157dfeb6dad19be3bfe66a59b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.411ex; height:2.509ex;" alt="{\displaystyle H_{B}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> can be seen to be the reproducing kernel Hilbert spaces with corresponding feature maps <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi _{A}:X\rightarrow \mathbb {R} ^{p}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi _{A}:X\rightarrow \mathbb {R} ^{p}}</annotation>

</semantics>

</math><img src="./a7977358178a90d60ae2112631d7184b8d603ad9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.411ex; height:2.676ex;" alt="{\displaystyle \Phi _{A}:X\rightarrow \mathbb {R} ^{p}}" loading="lazy">, given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi _{A}(x)=(a_{1}(x),...,a_{p}(x))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi _{A}(x)=(a_{1}(x),...,a_{p}(x))}</annotation>

</semantics>

</math><img src="./6e7bf4a6a38eb7dc43350fd8c04339ff76bc8886.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:27.21ex; height:3.009ex;" alt="{\displaystyle \Phi _{A}(x)=(a_{1}(x),...,a_{p}(x))}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi _{B}:X\rightarrow \mathbb {R} ^{q}}">

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi _{B}:X\rightarrow \mathbb {R} ^{q}}</annotation>

</semantics>

</math><img src="./fdcc83a004c89e4f195ea030167b66c84dfd6b62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.356ex; height:2.676ex;" alt="{\displaystyle \Phi _{B}:X\rightarrow \mathbb {R} ^{q}}" loading="lazy">, given by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi _{B}(x)=(b_{1}(x),...,b_{q}(x))}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi _{B}(x)=(b_{1}(x),...,b_{q}(x))}</annotation>

</semantics>

</math><img src="./0d2fb881dc8ae7160fab24a9a2de4111faebc292.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.69ex; height:3.009ex;" alt="{\displaystyle \Phi _{B}(x)=(b_{1}(x),...,b_{q}(x))}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi :X\rightarrow \mathbb {R} ^{p+q}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi :X\rightarrow \mathbb {R} ^{p+q}}</annotation>

</semantics>

</math><img src="./7d055c3cba52253e662cbf855aca7f67c5d70604.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.981ex; height:2.509ex;" alt="{\displaystyle \Phi :X\rightarrow \mathbb {R} ^{p+q}}" loading="lazy">, given by the concatenation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Phi _{A},\Phi _{B}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Phi _{A},\Phi _{B}}</annotation>

</semantics>

</math><img src="./d047de2628077609e15afdfee5b4f269bc2906de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.334ex; height:2.509ex;" alt="{\displaystyle \Phi _{A},\Phi _{B}}" loading="lazy">, respectively.

In the structured sparsity regularization approach to this scenario, the relevant groups of variables which the group norms consider correspond to the subspaces <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{A}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{A}}</annotation>

</semantics>

</math><img src="./b3f561a051435337d6fd20d1b3a2cb945fe97f3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.396ex; height:2.509ex;" alt="{\displaystyle H_{A}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{B}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{B}}</annotation>

</semantics>

</math><img src="./824d31f712318ce157dfeb6dad19be3bfe66a59b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.411ex; height:2.509ex;" alt="{\displaystyle H_{B}}" loading="lazy">. This approach promotes setting the groups of coefficients corresponding to these subspaces to zero as opposed to only individual coefficients, promoting sparse multiple kernel learning.

The above reasoning directly generalizes to any finite number of dictionaries, or feature maps. It can be extended to feature maps inducing infinite dimensional hypothesis

spaces.<a href="#cite_note-:7-16">[16]</a>

<div class="mw-heading mw-heading4"><h4 id="When_Sparse_Multiple_Kernel_Learning_is_useful">When Sparse Multiple Kernel Learning is useful</h4></div>

Considering sparse multiple kernel learning is useful in several situations including the following:

<ul><li>Data fusion: When each kernel corresponds to a different kind of modality/feature.</li>

<li>Nonlinear variable selection: Consider kernels <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K_{g}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K_{g}}</annotation>

</semantics>

</math><img src="./0e3715e6ef125b819798fc234d822d3378890af9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.994ex; height:2.843ex;" alt="{\displaystyle K_{g}}" loading="lazy"> depending only one dimension of the input.</li></ul>

Generally sparse multiple kernel learning is particularly useful when there are many kernels and model selection and interpretability are important.<a href="#cite_note-:7-16">[16]</a>

<div class="mw-heading mw-heading2"><h2 id="Additional_uses_and_applications">Additional uses and applications</h2></div>

Structured sparsity regularization methods have been used in a number of settings where it is desired to impose an a priori input variable structure to the regularization process. Some such applications are:

<ul><li><a href="Compressed_sensing" title="Compressed sensing">Compressive sensing</a> in <a href="Magnetic_resonance_imaging" title="Magnetic resonance imaging">magnetic resonance imaging</a> (MRI), reconstructing MR images from a small number of measurements, potentially yielding significant reductions in MR scanning time<a href="#cite_note-MRI-6">[6]</a></li>

<li>Robust <a href="Facial_recognition_system" title="Facial recognition system">face recognition</a> in the presence of misalignment, occlusion and illumination variation<a href="#cite_note-face_recognition-5">[5]</a></li>

<li>Uncovering <a href="Sociolinguistics" title="Sociolinguistics">socio-linguistic</a> associations between lexical frequencies used by Twitter authors, and the socio-demographic variables of their geographic communities<a href="#cite_note-sociolinguistic-7">[7]</a></li>

<li>Gene selection analysis of breast cancer data using priors of overlapping groups, e.g., biologically meaningful gene sets<a href="#cite_note-genetic-8">[8]</a></li></ul>

<ul><li><a href="Statistical_learning_theory" title="Statistical learning theory">Statistical learning theory</a></li>

<li><a href="Regularization_(mathematics)#Other_uses_of_regularization_in_statistics_and_machine_learning" title="Regularization (mathematics)">Regularization</a></li>

<li><a href="Sparse_approximation" title="Sparse approximation">Sparse approximation</a></li>

<li><a href="Proximal_gradient_method" title="Proximal gradient method">Proximal gradient methods</a></li>

<li><a href="Convex_analysis" title="Convex analysis">Convex analysis</a></li>

<li><a href="Feature_selection" title="Feature selection">Feature selection</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFRosascoPoggio,_Tomasso2014" class="citation book cs1">Rosasco, Lorenzo; Poggio, Tomasso (December 2014). A Regularization Tour of Machine Learning, MIT-9.520 Lectures Notes.</cite>

</li>

<li id="cite_note-groupLasso-2">^ <a href="#cite_ref-groupLasso_2-0">a</a> <a href="#cite_ref-groupLasso_2-1">b</a> <a href="#cite_ref-groupLasso_2-2">c</a> <a href="#cite_ref-groupLasso_2-3">d</a> <cite id="CITEREFYuanLin,_Y.2006" class="citation journal cs1">Yuan, M.; Lin, Y. (2006). "Model selection and estimation in regression with grouped variables". J. R. Stat. Soc. B. 68 (1): 49–67. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.79.2062">10.1.1.79.2062</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.1467-9868.2005.00532.x">10.1111/j.1467-9868.2005.00532.x</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6162124">6162124</a>.</cite>

</li>

<li id="cite_note-latentLasso-3">^ <a href="#cite_ref-latentLasso_3-0">a</a> <a href="#cite_ref-latentLasso_3-1">b</a> <a href="#cite_ref-latentLasso_3-2">c</a> <a href="#cite_ref-latentLasso_3-3">d</a> <a href="#cite_ref-latentLasso_3-4">e</a> <cite id="CITEREFObozinskiLaurentVert2011" class="citation arxiv cs1">Obozinski, G.; Laurent, J.; Vert, J.-P. (2011). "Group lasso with overlaps: the latent group lasso approach". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1110.0413">1110.0413</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/stat.ML">stat.ML</a>].</cite>

</li>

<li id="cite_note-LR18-4">^ <a href="#cite_ref-LR18_4-0">a</a> <a href="#cite_ref-LR18_4-1">b</a> <a href="#cite_ref-LR18_4-2">c</a> <a href="#cite_ref-LR18_4-3">d</a> <a href="#cite_ref-LR18_4-4">e</a> L. Rosasco. Lecture 10 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2014. Available at <a rel="nofollow" class="external free" href="https://www.mit.edu/~9.520/fall14/slides/class18/class18_sparsity.pdf">https://www.mit.edu/~9.520/fall14/slides/class18/class18_sparsity.pdf</a>

</li>

<li id="cite_note-face_recognition-5">^ <a href="#cite_ref-face_recognition_5-0">a</a> <a href="#cite_ref-face_recognition_5-1">b</a> <cite id="CITEREFJia2012" class="citation conference cs1">Jia, Kui; et al. (2012). "Robust and Practical Face Recognition via Structured Sparsity". In Andrew Fitzgibbon; Svetlana Lazebnik; Pietro Perona; Yoichi Sato; Cordelia Schmid (eds.). Computer Vision – ECCV 2012: 12th European Conference on Computer Vision, Florence, Italy, October 7-13, 2012 Proceedings, Part IV.</cite>

</li>

<li id="cite_note-MRI-6">^ <a href="#cite_ref-MRI_6-0">a</a> <a href="#cite_ref-MRI_6-1">b</a> <cite id="CITEREFChen2012" class="citation book cs1">Chen, Chen; et al. (2012). <a rel="nofollow" class="external text" href="https://papers.nips.cc/paper/4630-compressive-sensing-mri-with-wavelet-tree-sparsity">"Compressive Sensing MRI with Wavelet Tree Sparsity"</a>. Proceedings of the 26th Annual Conference on Neural Information Processing Systems. Vol. 25. Curran Associates. pp. 1115–1123.</cite>

</li>

<li id="cite_note-sociolinguistic-7">^ <a href="#cite_ref-sociolinguistic_7-0">a</a> <a href="#cite_ref-sociolinguistic_7-1">b</a> <cite id="CITEREFEisenstein2011" class="citation journal cs1">Eisenstein, Jacob; et al. (2011). "Discovering Sociolinguistic Associations with Structured Sparsity". Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics.</cite>

</li>

<li id="cite_note-genetic-8">^ <a href="#cite_ref-genetic_8-0">a</a> <a href="#cite_ref-genetic_8-1">b</a> <a href="#cite_ref-genetic_8-2">c</a> <cite id="CITEREFJacob2009" class="citation journal cs1">Jacob, Laurent; et al. (2009). "Group Lasso with Overlap and Graph Lasso". Proceedings of the 26th International Conference on Machine Learning.</cite>

</li>

<li id="cite_note-:0-9">^ <a href="#cite_ref-:0_9-0">a</a> <a href="#cite_ref-:0_9-1">b</a> <a href="#cite_ref-:0_9-2">c</a> <a href="#cite_ref-:0_9-3">d</a> <a href="#cite_ref-:0_9-4">e</a> <a href="#cite_ref-:0_9-5">f</a> <cite id="CITEREFVillaRosasco,_L.Mosci,_S.Verri,_A.2012" class="citation arxiv cs1">Villa, S.; Rosasco, L.; Mosci, S.; Verri, A. (2012). "Proximal methods for the latent group lasso penalty". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1209.0368">1209.0368</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.OC">math.OC</a>].</cite>

</li>

<li id="cite_note-:2-10">^ <a href="#cite_ref-:2_10-0">a</a> <a href="#cite_ref-:2_10-1">b</a> Blei, D., Ng, A., and Jordan, M. Latent dirichlet allocation. J. Mach. Learn. Res., 3:993–1022, 2003.

</li>

<li id="cite_note-:3-11">^ <a href="#cite_ref-:3_11-0">a</a> <a href="#cite_ref-:3_11-1">b</a> Bengio, Y. "Learning deep architectures for AI". Foundations and Trends in Machine Learning, 2(1), 2009.

</li>

<li id="cite_note-:4-12">^ <a href="#cite_ref-:4_12-0">a</a> <a href="#cite_ref-:4_12-1">b</a> S. Kim and E. Xing. Tree-guided group Lasso for multi-task regression with structured sparsity. In Proc. ICML, 2010.

</li>

<li id="cite_note-:1-13">^ <a href="#cite_ref-:1_13-0">a</a> <a href="#cite_ref-:1_13-1">b</a> <a href="#cite_ref-:1_13-2">c</a> <cite id="CITEREFJenattonAudibertBach2011" class="citation journal cs1">Jenatton, Rodolphe; Audibert, Jean-Yves; Bach, Francis (2011). "Structured Variable Selection with Sparsity-Inducing Norms". Journal of Machine Learning Research. 12 (2011): 2777–2824. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0904.3523">0904.3523</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009arXiv0904.3523J">2009arXiv0904.3523J</a>.</cite>

</li>

<li id="cite_note-:5-14">^ <a href="#cite_ref-:5_14-0">a</a> <a href="#cite_ref-:5_14-1">b</a> R. Jenatton, J. Mairal, G. Obozinski, and F. Bach. Proximal methods for sparse hierarchical dictionary learning. In Proc. ICML, 2010.

</li>

<li id="cite_note-:6-15">^ <a href="#cite_ref-:6_15-0">a</a> <a href="#cite_ref-:6_15-1">b</a> R. Jenatton, G. Obozinski, and F. Bach. Structured sparse principal component analysis. In Proc. AISTATS, 2009.

</li>

<li id="cite_note-:7-16">^ <a href="#cite_ref-:7_16-0">a</a> <a href="#cite_ref-:7_16-1">b</a> <a href="#cite_ref-:7_16-2">c</a> <a href="#cite_ref-:7_16-3">d</a> <cite id="CITEREFRosascoPoggio,_Tomaso2015" class="citation book cs1">Rosasco, Lorenzo; Poggio, Tomaso (Fall 2015). "Chapter 6". MIT 9.520 course notes Fall 2015.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-10-26" href="https://en.wikipedia.org/wiki/?title=Structured_sparsity_regularization&oldid=1182050179">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>